#include<iostream>
#include<stack>
#include<algorithm>
#include<string.h>
using namespace std;
extern string pre;
extern string ino;
class TreeNode{
	public:
	int lifTreeNode;
	int rifTreeNode;
	char data;
	TreeNode *lchild;
	TreeNode *rchild;
	TreeNode *father;
	int tag=0;
    int code;
	void printNode();
};
extern TreeNode *nownode;
extern TreeNode *Node;
class MyTree{
    public:
    TreeNode *Tree;
    int flag;
    int num;
	char node[100];
    MyTree();
    MyTree(const char *a);
    MyTree(const MyTree &T);
    void preOrderTraverse();
    void inOrderTraverse();
	void post(int ileft1,int iright1,int ileft2,int iright2);
    void postOrderTraverse();
    int countLeaf();
	int height(const TreeNode *Tree);
    int countHeight();
    bool isThreadedTree();
    bool inOrderThreading();
    TreeNode& locateNode(const char& v);
    TreeNode& preNode(const TreeNode& n);
    TreeNode& nextNode(const TreeNode& n);
};
class HuffmanTree{
	public:
	struct HTNode{
		int weight;
		int parent=-1;
		int lchild=-1;
		int rchild=-1;
	};
	HTNode *array;
	int *w;
	int num;
	HuffmanTree(const int& n, const int *a);
	void printHuffmanCodes();
};


